Mass storage devices that provide data storage that can be written to and read from by another entity such as a host can improve their performance through the use of algorithms that predict what the host will request before the host actually requests it. For example, a prediction algorithm may detect that a host has requested data from sequential sectors in a memory and predict, based on that observation, that the host will be likely or not likely to continue to request data from subsequent sequential sectors. If the prediction algorithm determines that the host is likely to continue requesting data from sequential sectors in memory, the prediction algorithm may cause the memory storage device to pre-fetch data from the next logical sector or sectors and store that data in a buffer so that if the host does request that data, the memory storage device can supply that data without delay. Prediction algorithms can significantly improve the performance of mass data storage systems that use as their primary storage memory that has a relatively slow or widely varying access time, such as hard disk drives or remote storage, or memory that provides data only in large chunks from which the portion of desired data must then be extracted, e.g., devices that use NAND FLASH memory, such as USB drives and solid state drives.
When the prediction algorithm guesses correctly, i.e., the data which is pre-fetched was the data that the host next asked for, the time between when the host requests the data and the when the device provides the data can be greatly reduced. However, should the prediction algorithm guess incorrectly, the pre-fetched data is not needed and is discarded. Meanwhile, the device must fetch the correct data, which is then provided to the host after some delay.
FIG. 1 is a flowchart illustrating a conventional method for performing host sequential reads. At step 100, a stream is detected as a candidate for predictive pre-fetching, or read buffering. For example, a memory device may detect that the host has performed a threshold number of sequential reads and from that point on perform a read-ahead or pre-fetch every time it receives another sequential read from the host. In response to detecting a candidate stream for pre-fetch, at step 102 data is pre-fetched from mass storage memory into a buffer memory in anticipation of subsequent reads.
The process waits at step 104 until a subsequent read is detected. If an I/O read is detected, at step 106 the requested data is output from the buffer memory. At step 108, additional data is pre-fetched from mass storage memory into the buffer memory. In other words, in the conventional approach illustrated in FIG. 1, once a stream is identified as a candidate for pre-fetch, additional data is pre-fetched from the mass storage memory into the buffer memory every time an I/O read occurs.
However, this approach has some disadvantages because it does not take into account the size of the data accesses. For example, once the conventional prediction algorithm illustrated in FIG. 1 activates the read-ahead operations, it pre-fetches additional data every time the device receives a read command from the host, regardless of the amount of data that the read command asked for. Two examples illustrate the weaknesses of this conventional approach:
In the first example, a host requests X amount of data with every read command, but only ½X of data is moved from the mass storage memory into the buffer memory after each read command. Since the data is drained from the buffer memory faster than the buffer memory is being replenished, the buffer memory will inevitably run out of data, a condition referred to as an underrun. In the conventional method described above, any time the host requests, on average, more data for every read command than is pre-fetched at the end of each read command, the buffer memory will eventually underrun, unless the host stops requesting data from the stream, e.g., the data stream terminates.
In the second example, a host requests X amount of data with every read command, but 2X amount of data is moved from mass storage memory into the buffer memory after each read command. Since the data is drained from the buffer memory slower than the buffer memory is being filled, the buffer memory will inevitably run out of memory, or overrun (or the buffer memory will continue to increase in size until there is no more memory in the system available for it to use.) In the conventional method described above, any time the host requests, on average, less data for every read command than is pre-fetched at the end of each read command, the buffer memory will eventually overrun, unless the host stops requesting data from the stream.
FIGS. 2A-2D show steps of an example operation according to the conventional process shown in FIG. 1. In FIG. 2A, block 1, an incoming read command, R7, is identified as being seventh in a series of read accesses to a contiguous set of logical block addresses within a mass storage memory 200 and thus part of a read data stream that is a candidate for read buffering. At block 2, some amount of a buffer memory is set aside as a read buffer 202 for the read data stream. In the example shown in FIGS. 2A-2D, read buffer 202 is divided into six identically-sized portions, referred to herein as buffers 1 through 6. At block 3, data predicted to be part of the read data stream will be pre-fetched into read buffer 202 from mass storage memory 200. This data transfer is shown as a set of arrows 4, which fill buffers 1 through 4 of read buffer 202.
In FIG. 2B, block 5, the portion of the pre-fetched data that was requested by R7 and shown in FIG. 2B as the darkly-colored portion of buffer 1 of read buffer 202 is provided to the host from read buffer 202. This data transfer is shown as arrow 6.
In FIG. 2C, another read command, R8, is received. The data requested by R8 is provided to the host from read buffer 202. This data transfer is shown as arrow 7. At block 8, once read command R8 has completed, this triggers a predictive pre-fetch of more data from mass storage memory 200 into read buffer 202. This data transfer is shown as arrow 9.
In FIG. 2D, block 10, some portion of read buffer 202 is released. Another read command, R9, is received. The data requested by R9 is provided to the host from read buffer 202. This data transfer is shown as arrow 11. At block 12, once read command R9 has completed, this triggers a predictive pre-fetch of more data from mass storage memory 200 into read buffer 202. This data transfer is shown as arrow 13.
In the example shown in FIGS. 2A through 2D it can be seen that the buffer memory is being filled faster than it is being drained. If this trend continues the buffer memory will overflow.
A buffer memory may be used to increase performance of sequential I/O writes as well, by accumulating multiple, sequential write data into the buffer memory and writing the accumulated data from the buffer memory into the mass storage memory in a single transfer. A conventional approach is shown in FIG. 3.
FIG. 3 is a flowchart illustrating a conventional method for performing host sequential writes. At step 300, a candidate stream for write buffering is detected. In response to detecting a candidate stream for write buffering, at step 302 some amount of buffer memory is reserved for the candidate stream. The process then waits at step 304 until a subsequent sequential I/O write of more stream data is detected, at which time the process goes to step 306. At step 306, data from the sequential write starts to fill the buffer memory rather than being written directly to the mass storage memory. As long as there is more data to be written, which is the condition that is being tested at step 308, the process will return to step 306 and write data will continue to be written to the buffer memory. Once all of the data has been written to buffer memory, the process goes to step 310. At step 310, write data is flushed from buffer memory to mass storage memory.
The process shown in FIG. 3 has some disadvantages, however. Like the conventional sequential read process shown in FIG. 1, the conventional sequential write process shown in FIG. 3 also does not take into account the size of the data accesses More specifically, in the conventional process shown in FIG. 3, data is flushed from the buffer memory to mass storage memory only after the write is complete. Two examples illustrate the weaknesses of this conventional approach:
In the first example, each write command sends a large amount of data. Because the conventional method shown in FIG. 3 does not flush the write buffer until after the write has completed, a large amount of buffer memory remains occupied and unavailable for use for longer than is absolutely necessary. When writing a large amount of data, this can cause a buffer overflow.
In the second example, each write command sends a small amount of data. If the conventional method shown in FIG. 2 flushes data from buffer memory after every write whether or not the buffer is full this method does not take full advantage of the benefits of writing data to the mass storage memory in large chunks at a time. If the mass storage memory is NAND FLASH, for example, it would be better to wait make one write to a page of FLASH memory than to make two writes to the same page of FLASH memory, e.g., where the first write fills the first half of the page and the second write fills the second half of the page.
FIGS. 4A-4G show steps of an example operation according to the conventional process shown in FIG. 1. In FIG. 4A, block 1, an incoming write command, W7, is identified as being seventh in a series of writes to a contiguous set of logical block addresses within a mass storage memory 400 and thus part of a candidate write data stream. At block 2, some amount of a buffer memory is set aside as a write buffer 402 for the write data stream. In the example illustrated in FIGS. 4A-4G, write buffer 402 is subdivided into six portions, buffers 1 through 6. At block 3, the write data is stored in write buffer 402 for later transfer to a mass storage memory 400. Storing the write data from W7 into write buffer 402 is shown as arrow 4, which indicates that the write data was stored into buffer 1 of write buffer 402.
In FIG. 4B, another write command, W8, is received. The write data from W8 is stored into write buffer 402. This data transfer is shown as arrow 5. At block 6, once write command W8 has completed, buffers 1 through 6 are checked to see if any may be flushed and released. In the example shown in FIG. 4B, buffer 1 is flushed, shown as arrow 7, but buffer 2 is not flushed yet.
In FIG. 4C, block 8, buffer 1 of write buffer 402 is released. Another write command, W9, is received. The write data from W9 is stored into write buffer 402. This data transfer is shown as arrow 9. In the example shown in FIG. 4C, the write data from W9 fills nearly 3 buffers of write buffer 402.
In FIG. 4D, block 10, once write command W9 has completed, buffers 1 through 6 are checked to see if any may be flushed and released. In the example shown in FIG. 4D, the completion of W9 triggers a flush of buffers 2, 3, and 4 of write buffer 402. In FIG. 4D, buffer 2 of write buffer 402 is flushed to mass storage memory 400. This data transfer is shown as arrow 11.
In FIG. 4E, block 12, buffer 2 of write buffer 402 is released and buffer 3 of write buffer 402 is flushed to mass storage memory 400. This data transfer is shown as arrow 13.
In FIG. 4F, block 14, buffer 3 of write buffer 402 is released and buffer 4 of write buffer 402 is flushed to mass storage memory 400. This data transfer is shown as arrow 15.
In FIG. 4G, block 12, buffer 4 of write buffer 402 is released. Buffer 5 of write buffer 402 still contains write data but is not yet full and so is not flushed to mass storage memory 400.
In the example shown in FIGS. 4A through 4G it can be seen that the write buffer flushed only after a write command is completed. As a result, write buffer 402 holds write data for longer than is necessary. If multiple writes of large amounts of data are received in a row, write buffer 402 may overflow.
Accordingly, in light of these disadvantages associated with conventional methods for handling sequential reads and writes involving mass storage memory, there exists a need for methods, systems, and computer readable media for optimization of host sequential reads or writes based on volume of data transfer.